/**
 * 给你一个链表的头节点head，请你编写代码，反复删去链表中由 总和值为 0 的连续节点组成的序列，直到不存在这样的序列为止。
 *
 * 删除完毕后，请你返回最终结果链表的头节点。
 *
 *
 *
 * 你可以返回任何满足题目要求的答案。
 *
 * （注意，下面示例中的所有序列，都是对ListNode对象序列化的表示。）
 *
 * 来
 * 思路：定义一个值为 0 的虚拟头节点，当做原链表新的头节点，即 dummyHead.next = head；定义一个 pre 指针指向虚
 * 拟头节点作为原链表头节点的前驱节点（方便进行删除操作）。
 * 定义一个指针 p 指向 pre 指向节点的后一个节点（开始时，p 指向原链表的头节点）；然后 p 指针开始遍历链表，
 * 每遍历一个节点就将该节点值与之前节点值总和进行相加得到新的 sum：
 * 若 sum == 0，则需要进行删除（将 pre 指针和 p 指针指向节点(包括 p 指针指向的节点)中间的节点删除），即
 *
 * pre.next = p.next 然后直接退出循环：
 * 若此时 p 指针已经走到了链表的末尾，则令 pre 指针后移一位并且 p 指向 pre 指向节点的下一节点重新进行判
 * 断以及删除；
 * 若此时 p 指针没有走到链表的末尾，则令 pre 指针不动，p 指针继续从 pre 指针指向节点的下一节点开始遍历
 * 链表并进行比较和删除操作；若 sum != 0，则 p 指针继续后移，继续对下一节点进行判断，直到找到使 sum 值为 0 的节点或遍历到链表的结尾为
 * 止。
 *
 * 注意：只有当 p 指针指向链表末尾时，pre 指针才后移；否则，则 pre 指针不动，令 p 指针在删除后的链表中
 * 继续从头开始遍历。
 *
 * if (p == null) pre = pre.next;
 *
 * 示例：head = [0, 1, -1] dummyHead = [0, 0, 1, -1]
 *
 * 若没有这个判断，则只要跳出循环就将 pre 指针后移一位，则会出现问题。 开始时，pre 指向第一个 0 并且 p
 *
 * 指向第二个 0，此时 sum = 0 则进行删除并且 pre = pre.next，此时 dummyHead = [0, 1, -1]； pre 指向 1 并
 * 且 p 指向 -1，此时 sum = -1，p 继续后移为 null 结束循环，最后会输出 [1, -1] 答案错误。
 * 若有这个判断，当将 p 指针指向的 0 删除后，p 没有指向链表末尾 pre 指针不进行移动，此时 dummyHead =
 * [0, 1, -1]； pre 指针仍指向 0，此时 p 指针指向 1，sum = 1 则 p 指针后移；p 指向 -1，此时 sum = 0, 则进行
 * 删除操作，此时 dummyHead = [0] 结束，返回 dummyHead.next 即可。
 * https://leetcode.cn/problems/remove-zero-sum-consecutive-nodes-from-linked-list/submissions/
 * 思路：前缀和
 * 题解：https://leetcode.cn/problems/remove-zero-sum-consecutive-nodes-from-linked-list/solution/qian-zhui-he-dan-lian-biao-de-qian-zhui-kwr05/
 */
class RemoveZeroSumSublists {
    public ListNode removeZeroSumSublists(ListNode head) {
        ListNode dummy=new ListNode(0);
        dummy.next=head;
        Map<Integer,ListNode> map =new HashMap<>();
        int sum=0;
        for(ListNode d=dummy;d!=null;d=d.next) {
            sum+=d.val;
            map.put(sum,d);
        }
        sum=0;
        for(ListNode d= dummy;d!=null;d=d.next) {
            sum+=d.val;
            d.next=map.get(sum).next;
        }
        return dummy.next;
    }
}